#include <iostream>

template <typename T>
struct LinkNode {
    T val;
    LinkNode* next = NULL;
};

// 头插法
template <typename T>
void insert_head(LinkNode<T>* src, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;
    node->next = src->next;
    src->next = node;
}

// 尾插法
template <typename T>
void insert_end(LinkNode<T>* src, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;

    while(src->next)
    {
        src = src->next;
    }
    node->next = src->next;
    src->next = node;
}

// 删除第idx个元素，链表有头结点，idx>0，不赋值方法
template <typename T>
void del_val_by_node(LinkNode<T>* src, unsigned int idx)
{
    if(src == NULL || src->next == NULL)
        return;
    
    unsigned int count = 0;
    while(src && src->next)
    {
        if(idx-1 == count)
        {
            LinkNode<T>* node = src->next;
            src->next = src->next->next;
            delete node;
            break;
        }
        count += 1;
        src = src->next;
    }
}

// 第idx个位置后插入元素，链表有头节点，idx>0
template <typename T>
void insert_val(LinkNode<T>* src, unsigned int idx, T val)
{
    LinkNode<T>* node = new LinkNode<T>;
    node->val = val;

    unsigned int count = 0;
    while(src)
    {
        if(idx == count)
        {
            node->next = src->next;
            src->next = node;
            break;
        }
        count += 1;
        src = src->next;
    }
}

// 注销链表
template <typename T>
void release_linklist(LinkNode<T>* src)
{
    while(src)
    {
        LinkNode<T>* node = src;
        src = src->next;
        delete node;
    }
}

int main()
{
    LinkNode<int>* head = new LinkNode<int>;
    head->val = -1;

    for(int i = 0; i < 5; i++)
        //insert_end(head, i);
        insert_head(head, i);
    del_val_by_node(head, 1);
    insert_val(head, 4, 1);
    while(head)
    {
        std::cout << head->val << std::endl;
        head = head->next;
    }
    release_linklist(head);
    return 0;
}